import java.util.HashMap;

class Solution {
    public int[] twoSum1(int[] nums, int target) {
        HashMap<Integer,Integer> map=new HashMap<>();
        int [] arr=new int[]{0,0};
        for(int i=0;i<nums.length;i++){
            int sum=target-nums[i];
            if(map.containsKey(sum)){
                arr[0]=sum;
                arr[1]=nums[i];
                return arr;
            }else{
                map.put(nums[i],1);
            }
        }
        return arr;
    }
    public int[] twoSum(int[] nums, int target) {
        int left=0,right=nums.length-1;
        int mid=0;
        int [] arr=new int[]{0,0};
       for(int i=0;i<nums.length;i++){
           left=i;
            int sum=target-nums[left];
            while(left<=right){
            mid=(left+right)/2;
            if(nums[mid]>sum){
                right=mid-1;
            }else if (nums[mid]<sum){
                left=mid+1;
            }else{
                 arr[1]=nums[mid];
                 arr[0]=nums[i];
                 return  arr;
            }
            }
        }
         return arr;
    }
}